#include "SingleLinkListStatic.h"
#include <stdio.h>
void Init_SLinkList(SLinkList S)//初始化一个空的线性表S
{
	DataType i;
	puts("==开始初始化静态单链表S！==");
	for(S[0].data=0,i=0;i<MAXSIZE;i++)//头节点在0位置，它的数据域data是整个链表元素的个数，即顺序表长，表长初始化为0
	{
		S[i].cur=NULLNODE;//NULLNODE代表空指针
	}
	puts("==静态单链表S初始化完成！==");
}
void Head_Init_SLinkList(SLinkList S)//头插法建立静态单链表S
{
	DataType i,n,k,co;
	Point p=SLHead;//定义一个p指向头节点
	fflush(stdin);
	printf("\n开始头插法(以f结束)：");
	for(i=0;i+1<MAXSIZE;i++)
	{
		k=scanf("%d",&n);
		if(k==0)
		{
			break;
		}
		else
		{
			co++;
			S[i+1].data=n;
			S[i+1].cur=S[p].cur;
			S[p].cur=i+1;
			S[0].data++;
		}
	}
	fflush(stdin);
}
void Tail_Init_SLinkList(SLinkList S)//尾插法建立静态单链表S
{
	DataType i,n,k,co;
	Point p=SLHead;//定义一个p指向头节点 
	fflush(stdin);
	printf("\n开始尾插法(以f结束)：");
	for(i=0;i+1<MAXSIZE;i++)
	{
		k=scanf("%d",&n);
		//printf("k=%d,n=%d\n",k,n); 
		if(k==0)
		{
			break;
		}
		else
		{
			co++;
			S[i+1].data=n;
			S[i+1].cur=S[p].cur;
			S[p].cur=i+1;
			p=i+1;
			S[0].data++;
		}
	}
	fflush(stdin);
}
//Status DestoryList(int* L);//销毁线性表S
void ClearList(SLinkList S)//清空线性表S
{
	DataType i;
	puts("\n==开始清空静态单链表S！==");
	for(S[0].data=0,i=0;i<MAXSIZE;i++)//头节点在0位置，它的数据域data是整个链表元素的个数，即顺序表长，表长初始化为0
	{
		S[i].cur=NULLNODE;//NULLNODE代表空指针
	}
	puts("==清空静态单链表S完成！==");
}
Status IsEmptySLinkList(SLinkList S)//若S为空表，则返回TRUE,否则返回FALSE
{
	if(S[0].data==0)
	{
		return TRUE;
	}
	else
	{
		return FALSE;
	}
}
DataType SLinkListLength(SLinkList S)//返回S中数据元素个数
{
	//printf("\nS中当前元素个数是：%d\n",S[0].data);
	return S[0].data; 
}
DataType GetElem(SLinkList S,DataType i,Pt e)//用e返回S中第i个元素的值,操作成功返回OK，否则返回ERROR
{
	if(IsEmptySLinkList(S)==TRUE)
	{
		printf("\n当前表空，不能查询！\n",i);
		return ERROR;
	}
	if(i>SLinkListLength(S)||i<1) 
	{
		printf("\n当前查询位置%d不合法！\n",i);
		return ERROR;
	}
	int p=S[0].cur,co=0;
	while(p!=-1)
	{
		co++;
		if(co==i)
		{
			*e=S[p].data;
			return OK;
		}
		p=S[p].cur;
	}
}
DataType LocateElem(SLinkList S,DataType e)//返回e在S中的位置,有该数据元素则返回其位置，否则返回0
{
	if(IsEmptySLinkList(S)==TRUE)
	{
		return ERROR;
	}
	int p=S[0].cur,co=0;
	while(p!=-1)
	{
		co++;
		if(S[p].data==e)
		{
			return co;
		}
		p=S[p].cur;
	}
	return ERROR;
}
Status PriorElem(SLinkList S,DataType e,Pt proe)//若若e是S的数据元素，且不是第一个，则用proe返回它的前驱。操作成功返回OK,否则返回-6699
{
	if(IsEmptySLinkList(S)==TRUE)
	{
		*proe=-6699; 
		printf("\n当前表S空，不能查询%d的前驱值！\n",e);
		return ERROR;
	}
	if(IsEmptySLinkList(S)!=TRUE&&LocateElem(S,e)==ERROR)
	{
		*proe=-6699; 
		printf("\n值%d不在表S中，无法返回其前驱值！\n",e);
		return ERROR;
	}
	if(LocateElem(S,e)==1)
	{
		*proe=-6699; 
		printf("值%d是表S第一个元素，无前驱值！\n",e);
		return ERROR;
	}
	int p=S[0].cur,co=0;
	while(p!=-1)
	{
		co++;
		if(co==LocateElem(S,e)-1)
		{
			*proe=S[p].data;
			return OK;
		}
		p=S[p].cur;
	}
}
Status NextElem(SLinkList S,DataType e,Pt nexte)//若e是S的数据元素，且不是最后一个，则用nexte返回它的后继。操作成功返回OK,否则返回-6699
{
	if(IsEmptySLinkList(S)==TRUE)
	{
		*nexte=-6699;
		printf("\n当前表S空，不能查询%d的后继值！\n",e);
		return ERROR;
	}
	if(IsEmptySLinkList(S)!=TRUE&&LocateElem(S,e)==ERROR)
	{
		*nexte=-6699;
		printf("\n值%d不在表S中，无法返回其后继值！\n",e);
		return ERROR;
	}
	if(LocateElem(S,e)==S[0].data)
	{
		*nexte=-6699;
		printf("值%d是表S最后一个元素，无后继值！\n",e);
		return ERROR;
	}
	int p=S[0].cur,co=0;
	while(p!=-1)
	{
		co++;
		if(co==LocateElem(S,e)+1)
		{
			*nexte=S[p].data;
			return OK;
		}
		p=S[p].cur;
	}
}
Status SLinkListInsert(SLinkList S,DataType i,DataType e)//在S第i个位置之前插入新的元素e，S长度加1,成功操作返回OK，否则返回ERROR
{

	if(SLinkListLength(S)==MAXSIZE) 
	{
		printf("\n当前表S已满，不能再插入！\n");
		return ERROR;
	}
	if(i>SLinkListLength(S)+1||i<1)
	{
		printf("\n插入位置%d不合法，不能再插入！\n",i);
		return ERROR;
	}
	int p=SLHead,q,co=-1; 
/*方法一： 容易产生假溢出，但是分配空间时代码简单，容易想到 
	q=S[0].data+1;//给待插入的元素e分配一个位置 
	S[q].data=e; //将e放入分配的位置
*/
/*方法二： 不容易产生假溢出现象，充分利用每个数组位置
	int j,f=0;
	for(int j=1;j<MAXSIZE;j++)
	{
		if(S[j].cur==NULLNODE)
		{
			while(p!=-1)
			{
				if(S[p].cur==-1)
				{
					break;
				}
				p=S[p].cur;
			}//找到尾结点的指针值，即数组下标 
//			printf("尾结点数组下标是：%d\n",p); 
			if(p==j)
			{
				continue;
			}
			else
			{
				q=j;
				S[q].data=e;//不是则用作分配新空间  
//				printf("新分配的空间是数组的%d位置！\n",q);
				break; 
			}
		}
	}
*/ 
	int j,f=0;
	for(int j=1;j<MAXSIZE;j++)
	{
		if(S[j].cur==NULLNODE)
		{
			while(p!=-1)
			{
				if(S[p].cur==-1)
				{
					break;
				}
				p=S[p].cur;
			}//找到尾结点的指针值，即数组下标 
//			printf("尾结点数组下标是：%d\n",p); 
			if(p==j)
			{
				continue;
			}
			else
			{
				q=j;
				S[q].data=e;//不是则用作分配新空间  
//				printf("新分配的空间是数组的%d位置！\n",q);
				break; 
			}
		}
	}

	p=SLHead;
	while(p!=-1)
	{
		co++;
		if(co==i-1)
		{
			S[q].cur=S[p].cur;
			S[p].cur=q; 
			S[0].data++;
			return OK;
		}
		p=S[p].cur;
	}
}
DataType SLinkListDelete(SLinkList S,DataType i,Pt e)//删除S的第i个数据元素，并用e返回其值，S长度减1,操作成功返回删除的值，否则返回ERROR
{
	if(SLinkListLength(S)==0) 
	{
		printf("\n当前表S空，不能删除任何值！\n");
		return ERROR;
	}
	if(i>SLinkListLength(S)||i<1)
	{
		printf("\n删除位置%d不合法，不能删除任何值！\n",i);
		return ERROR;
	}
	int p=SLHead,co=-1; 
	int q=0;//q用来保存i之前位置的指针 
	while(p!=-1)
	{
		co++;
		if(co==i-1)
		{
			q=p;
//			printf("i之前的是%d=%d,co=%d\n",q,S[q].data,co);
		}
		if(co==i) 
		{	
//		    printf("%d %d是%d,指向%d",p,i,S[p].data,S[p].cur);
			*e=S[p].data;
			S[q].cur=S[p].cur;
			S[p].cur=NULLNODE;
			S[0].data--;
			return OK;
		}
		p=S[p].cur;
	}
}
Status SLinkListTraverse(SLinkList S)//依次对LS每个数据元素调用函数,成功遍历返回OK，否则返回ERROR
{
	int p=S[0].cur;
	if(p==-1)
	{
		printf("【遍历检查】|长度：%d|头结点-->NULL\n",S[0].data);
	}
	else
	{
		printf("\n【遍历检查】|长度：%d|头结点",S[0].data);
		while(p!=-1)
		{
	
			//printf("--->S[%d].data=%d,S[%d].cur=%d",p,S[p].data,p,S[p].cur);
			printf("--->%d",S[p].data);
			p=S[p].cur;
		}
		printf("-->NULL\n"); 
	}
	return OK;
}